package com.zyx.javademo.recursiontree;

import com.alibaba.fastjson.JSON;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.StringUtils;

import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * <p>递归树</p>
 *
 * @author Yaxi.Zhang
 * @since 2022/8/13 16:43
 */
public class RecursionTree {

    public static void main(String[] args) {
        /*
                 1            2
               /  \         /  \
              3    4       5   11
             / \         / | \
            6   7       8  9  10
         */
        List<Menu> daoMenuList = Stream.of(
                new Menu().setId("1").setName("menu-1").setParentId(null),
                new Menu().setId("2").setName("menu-2").setParentId(null),
                new Menu().setId("3").setName("menu-3").setParentId("1"),
                new Menu().setId("4").setName("menu-4").setParentId("1"),
                new Menu().setId("5").setName("menu-5").setParentId("2"),
                new Menu().setId("6").setName("menu-6").setParentId("3"),
                new Menu().setId("7").setName("menu-7").setParentId("3"),
                new Menu().setId("8").setName("menu-8").setParentId("5"),
                new Menu().setId("9").setName("menu-9").setParentId("5"),
                new Menu().setId("10").setName("menu-10").setParentId("5"),
                new Menu().setId("11").setName("menu-11").setParentId("2")
        ).collect(Collectors.toList());
        // 查看结果
        System.out.println(JSON.toJSONString(daoMenuList));
        System.out.println("==================== calculate ====================");
        List<Menu> resultList = getMenuTree(daoMenuList);
        System.out.println(JSON.toJSONString(resultList));
    }

    /**
     * <p>依据dao层数据获取最终的递归树</p>
     *
     * @param daoMenuList dao层树结构
     * @return 调整后的递归树
     */
    public static List<Menu> getMenuTree(List<Menu> daoMenuList) {
        // 找到一级菜单
        List<Menu> menuList = daoMenuList.stream().filter(menu -> StringUtils.isBlank(menu.getParentId())).collect(Collectors.toList());
        if (CollectionUtils.isEmpty(menuList)) {
            return Collections.emptyList();
        }
        // 找到parentId与子目录的映射
        Map<String, List<Menu>> parentMap = daoMenuList.stream()
                .filter(menu -> menu.getParentId() != null)
                .collect(Collectors.groupingBy(Menu::getParentId));
        // 为一级菜单设置子菜单， getChild是递归调用的
        for (Menu menu : menuList) {
            menu.setChildMenus(getChild(menu.getId(), parentMap));
        }
        return menuList;
    }

    /**
     * <p>递归查找子菜单</p>
     * <p>&emsp;&emsp;1.先得到所有的菜单父id与当前父id直接子目录的映射关系</p>
     * <p>&emsp;&emsp;2.依据当前的目录id，找到所有的直接子目录</p>
     * <p>&emsp;&emsp;3.如果当前目录id对应的子目录为空，说明已经是叶子节点了，返回空集合</p>
     * <p>&emsp;&emsp;4.使用递归找子菜单的子菜单</p>
     *
     * @param id        当前菜单id
     * @param parentMap 剩余未查找的节点
     * @return 最终结果
     */
    private static List<Menu> getChild(String id, Map<String, List<Menu>> parentMap) {
        // 子菜单
        List<Menu> childList = parentMap.get(id);
        // 递归退出条件
        if (CollectionUtils.isEmpty(childList)) {
            return Collections.emptyList();
        }
        // 把子菜单的子菜单再循环一遍
        for (Menu menu : childList) { // 没有url子菜单还有子菜单
            // 递归
            menu.setChildMenus(getChild(menu.getId(), parentMap));
        }
        return childList;
    }

}
